package cn.suchan.jianzhi.q51_array;

/**
 * 知识点：构建乘积数组
 * 题目描述
 * 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
 * 其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
 * # 原来就是不要i，我说看了半天没啥区别呢
 *
 * @author suchan
 * @date 2019/06/09
 */
public class Solution {

    /**
     * 直接遍历数组
     *
     * @param A
     * @return
     */
    public int[] multiply(int[] A) {
        int[] b = new int[A.length];
        for (int i = 0; i < b.length; i++) {
            int temp = 1;
            for (int j = 0; j < A.length; j++) {
                if (i != j) {
                    temp *= A[j];
                }
            }
            b[i] = temp;
        }
        return b;
    }

    /**
     * 所有元素乘积除以当前元素乘积（a[i]）即为b[i]，这里需要考虑数组中0的个数
     *
     * @param A
     * @return
     */
    public int[] multiply1(int[] A) {
        int[] b = new int[A.length];
        // 不管有没有0
        int prod = 1;
        // 去掉0
        int prodZero = 1;
        int zeroCount = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != 0) {
                // 计算数组中所有非零元素的乘积
                prodZero *= A[i];
            } else {
                // 计算数组中0的个数
                zeroCount++;
            }
            // 计算数组中所有元素的乘积
            prod *= A[i];
        }
        for (int i = 0; i < b.length; i++) {
            // 如果数组中存在一个以上值为0的元素，则所有元素乘积均为0
            if (zeroCount > 1) {
                b[i] = 0;
            } else {
                // 如果prod==0，说明数列中有一个0（可以进这一步说明0的个数肯定小于等于1个）
                // 当数列中只有一个0，且当前元素不为0，则其他元素的乘积肯定都是0
                if (prod == 0 && A[i] != 0) {
                    b[i] = 0;
                } else if (A[i] == 0) {
                    // 如果当前元素为0，则其他元素的乘积就是所有非零元素的乘积
                    b[i] = prodZero;
                } else {
                    // 如果数组中全为非零元素，则所有元素乘以当前元素的-1次方，即为除当前元素以外的所有元素乘积
                    b[i] = Double.valueOf(prod * Math.pow(A[i], -1)).intValue();
                }
            }
        }
        return b;
    }

    /**
     * 可以看出题目中所求的元素B[]即为下列每一行的乘积：
     * #        B0=    1   A1  A2  A3  ...  An-1  An
     * #        B1=    A0  1   A2  A3  ...  An-1  An
     * #        B2=    A0  A1  1   A3  ...  An-1  An
     * #        B3=    A0  A1  A2  1   ...  An-1  An
     * #        ...=   A0  A1  A2  A3  .1.  An-1  An
     * #        Bn-1=  A0  A1  A2  A3  ...   1    An
     * #        Bn=    A0  A1  A2  A3  ...  An-1  1
     * 将B中的元素按照1分为上下两个三角形，先将B中的元素乘以下三角的元素，再乘以上三角的元素。
     *
     * @param A
     * @return
     */
    public int[] multiply2(int[] A) {
        if (A == null || A.length <= 0) {
            return new int[0];
        }
        int[] b = new int[A.length];
        b[0] = 1;
        for (int i = 1; i < b.length; i++) {
            b[i] = b[i - 1] * A[i - 1];
        }
        // 借助一个中间变量存储上三角的乘积
        int temp = 1;
        for (int j = A.length - 2; j >= 0; j--) {
            temp = temp * A[j + 1];
            b[j] = b[j] * temp;
        }
        return b;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 0, 4, 5};
        Solution solution = new Solution();
        int[] b = solution.multiply2(a);
        for (int i = 0; i < b.length; i++) {
            System.out.println(b[i]);
        }
    }
}
